package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhangjy
 * @description 子集 II
 * <p>
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
 * <p>
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列
 * @date 2025/6/15 13:12
 */
public class SubsetsWithDup_90 {

    public static void main(String[] args) {
        SubsetsWithDup_90 subsetsWithDup90 = new SubsetsWithDup_90();

        int[] nums = {1, 2, 2};
        subsetsWithDup90.subsetsWithDup(nums).forEach(System.out::println);
    }

    /**
     * 个解：递归回溯
     * <p>
     * 思路；转换为，在有重复元素的nums中，找所有目标组合，不过组合的元素个数可变化
     * <p>
     * 分析：
     * <p>
     * 1.nums元素重复，但是每个元素只能用一次（但组合总和里，元素可以重复使用）
     * <p>
     * 2.used什么时候初始化？——查找组合前初始化，每种组合元素个数情况下，used数组都是nums.length。<br/>
     * 因为，若在每层subsetSize时根据遍历层数i来初始化，即used = new int[i]；那么，当i=subsetSize=1时，递归回溯找元素也会判断所有nums的元素，此时记录nums[1]，但是used={0}，判断used[1]就会出现数组越界。<br/>
     * <p>
     * 3.为什么startIndex=i+1？——这里是找组合，上一层的元素使用过后，下一层不会再次使用。
     * <p>
     * 4.去重逻辑同全排列 II，分为树层、树枝去重。
     */
    public List<List<Integer>> ans = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public int[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // nums元素可重复，每种子集中，找出对应所有组合
        // 转换为，可重复nums，找出含指定元素个数的所有组合（个数∈[0, nums.length]）

        // 1.返回值void；入参：nums、path、ans、subsetSize、startIndex，used
        // 循环处理subsetSize∈[0, nums.length]
        // used记录元素使用状态（用于搜索中去重）；
        // startIndex？——下一层递归的开始，因为这里是找组合，上一层的元素使用过后，下一层不会再次使用。
        // 2.递归终止条件
        // path的元素==subsetSize，则记录path，并结束本层递归
        // 3.搜索过程
        // 3.1.第一层for循环，处理每种subsetSize情况；每层调用backtrack
        // 3.2.第二层for循环，横向遍历，开始真正找目标组合/子集
        // 先去重；当前元素i==前一个元素i-1，且同一树层的前一个元素尚未使用过，则跳过处理当前元素i，完成去重。因为当元素值相同，i-1元素找到的所有目标结果，和i元素找到必定相同。
        // 记录元素
        // 向下递归
        // 回溯

        // 先排序
        Arrays.sort(nums);
        // 再查找每种子集元素个数情况下，所有目标组合
        used = new int[nums.length];
        for (int i = 0; i <= nums.length; i++) {
            backtrack(nums, i, 0);
        }
        return ans;
    }

    public void backtrack(int[] nums, int subsetSize, int startIndex) {
        // path记录的元素个数==当前要求子集元素个数，就记录path，并结束本层递归
        if (path.size() == subsetSize) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // 横向遍历，当前子集元素个数条件下，找出所有目标组合
        for (int i = startIndex; i < nums.length; i++) {
            // 1.树层去重
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)
                continue;

            // 2.记录元素
            // 不需要树枝去重，因为递归时
            path.add(nums[i]);
            used[i] = 1;

            // 3.向下递归
            // startIndex=i+1，是因为本题实际是找组合，使用过的元素及前面元素，下一层就不再使用
            backtrack(nums, subsetSize, i + 1);

            // 4.回溯
            path.remove(path.size() - 1);
            used[i] = 0;
        }
    }

}
